package org.example;

public class BinarySearch {


    /**
     * 普通写法
     * @param array 有序数组
     * @param target 目标值
     * @return
     */
    public static int binarySearch(int[] array, int target) {
        int i = 0, j = array.length -1;
        while (i <= j) {
            int m = (i + j) / 2; // Java默认向下取整
            if (array[m] < target) {
                i = m + 1;
            } else if (target < array[m]) {
                j = m - 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 优化版本V2 （右移运算）
     * @param array 有序数组
     * @param target 目标值
     * @return
     */
    public static int binarySearchV2(int[] array, int target) {
        int i = 0, j = array.length -1;
        while (i <= j) {
            int m = (i + j) >> 1; // 右移1位，解决int长度bug
            if (array[m] < target) {
                i = m + 1;
            } else if (target < array[m]) {
                j = m - 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 优化版本V3 （   ] 左毕右开区间使用
     * @param array 有序数组
     * @param target 目标值
     * @return
     */
    public static int binarySearchV3(int[] array, int target) {
//        int i = 0, j = array.length - 1 +1;
        int i = 0, j = array.length;
        while (i < j) { //去掉等于号相当于减少一次循环， 但是上面的循环长度 加 1了 抵消了一次 等价
            int m = (i + j) >> 1; // 右移1位，解决int长度bug
            if (array[m] < target) {
                i = m + 1;
            } else if (target < array[m]) {
//                j = m -1 +1;
                j = m;
            } else {
                return m;
            }
        }
        return -1;
    }
}
